package DataStructure.BFS;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author：DijaH
 * @Date：2023/1/5 8:39 下午
 * @Version：1.0.0
 * @Description：
 * 解开密码需要多少次
 * 一个带有四个圆形波轮的转盘锁，每个波轮有0～9个数字，在9的位置可以变为0，在0的位置也可以变为9
 * 有一套死亡数组和target，在转动的过程中，你要避免播出其中的任何一个密码
 * 请你计算出初始状态"0000" =》 target最少需要多少次。如果永远无法拨出返回-1
 */
public class OpenLock {

    //在这里BFS架构可以穷举出所有的密码，但是仍不能完成题目的要求。
    //问题：
    //1、会走回头路，比如从"0000" =》 1000，但是从1000还可以走到0000
    //1、终止条件？
    //1、对于deadends的处理
    public static int OpenTheLock(String [] deadends,String target){
        //记录需要跳过去的密码,continue;
        HashSet<String> deads = new HashSet<>();
        for (String deadend : deadends) {
            deads.add(deadend);
        }
        //记录走过哪些密码
        HashSet<String> visited = new HashSet<>();
        Queue<String> q = new LinkedList<>();
        //放到队列中
        q.offer("0000");
        int depth = 0;
        while (!q.isEmpty()){
            //只要队列不为空就继续循环
            int size = q.size();
            for (int i = 0; i < size; i++) {
                String cur = q.poll();
                if(deads.contains(cur)){
                    //如果死亡set中有了就跳过
                    continue;
                }
                if(cur.equals(target)){
                    return depth;
                }
                //如果都没有的话，就可以继续拨动转盘
                //将一个节点的未遍历的相邻节点加入到队列中
                for (int j = 0; j < 4; j++) {
                    //往上拨动
                    String up = PlusOne(cur,j);
                    //往上拨动的之后，发现还没有访问过，就放到队列中去
                    if(!visited.contains(up)){
                        q.offer(up);
                        visited.add(up);
                    }
                    //往下拨动
                    String minus = MinusOne(cur,j);
                    if(!visited.contains(minus)){
                        q.offer(minus);
                        visited.add(minus);
                    }
                }
            }
            //在这里增加步数
            depth++;

        }
        return -1;
    }

    private static String MinusOne(String cur, int i) {
        //某一个数字往下拨动
       char[] curChar = cur.toCharArray();
       if (curChar[i] == '0'){
           curChar[i] = '9';
       }else {
           curChar[i] = (char) (curChar[i] - 1);
       }
       return new String(curChar);

    }

    private static String PlusOne(String cur, int i) {
        //某一个数字往上拨动
        char[] curChar = cur.toCharArray();
        if(curChar[i] == '9'){
            curChar[i] = '0';
        }else {
            curChar[i] -= 1;
        }
        return new String(curChar);
    }
}
